package algorithm.color2w.algorithm.linkedlist;

import java.util.Stack;

/**
 * @author wjl <br/>
 * @version 1.0
 * @ClassName: PalindromeLinkedList 回文链表的判定 <br/>
 * @Description: TODO<br />
 * @date: 2020/1/21 9:39<br/>
 */
public class PalindromeLinkedList {
    /*
    * Definition for singly-linked list.
    */
    public static class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
    }

    //1. 利用栈 ： 将链表入栈，在逐个出栈与原来的链表进行比较
    public static boolean isPalindrome1(ListNode head) {
        Stack<Integer> stack = new Stack();
        ListNode compareHead = head;
        while (null != head){
            stack.push(head.val);
            head = head.next;
        }
        boolean flag = true;
        while (null != compareHead){
            if (compareHead.val == stack.pop()){
                compareHead = compareHead.next;
            }else {
                //若当前链表不为true，链表指针会一直停留在当前节点，而stack会一直pop，最终导致栈抛出空异常
                flag = false;
//                return flag;
            }
        }
        return flag;
    }

    //2.
    public static boolean isPalindrome2(ListNode head) {
        return false;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(3);
        ListNode l5 = new ListNode(1);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        System.out.println(isPalindrome1(l1));
    }

}
